/*
 * @lc app=leetcode.cn id=312 lang=cpp
 *
 * [312] 戳气球
 */

// @lc code=start
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        //区间DP
        //f[i,j]表示从i打到j的气球的最大值；
        //不含i和j
        //要注意DP的次序
        vector<int> n (nums.size() + 2);
        vector<vector<int>> f(nums.size() + 2, vector<int>(nums.size() + 2));
        
        for(int i = 0; i < nums.size(); i++)
            n[i + 1] = nums[i];
        n[0] = 1;
        n[n.size() - 1] = 1;
        
        for(int len = 2; len < n.size(); len++)
            for(int i = 0; i + len < n.size(); i++){
                int j = i + len;
                for(int k = i + 1; k < j; k++)
                    f[i][j] = max(f[i][j], f[i][k] + f[k][j] + n[i] * n[j] * n[k]);
            }
        
        return f[0][n.size() - 1];
    }
};
// @lc code=end

